#include <stdio.h>
#include <stdlib.h>

static int  Node_num=0;
typedef struct Double_Cycle_Link_list Link_List_t;
typedef struct Double_Cycle_Link_list* pLink_List_t;

struct Double_Cycle_Link_list
{
    struct Double_Cycle_Link_list *prev;
    int data;
    struct Double_Cycle_Link_list *next;
};

// 有空节点的链表
// 头节点不存放数据
pLink_List_t Double_Cycle_Link_List_Init()
{
    pLink_List_t phead = (pLink_List_t)malloc(sizeof(Link_List_t));
    if (phead == NULL)
    {
        perror("Init Double_Cycle_Link_List fail");
        return phead;
    }
    phead->prev = phead;
    phead->data = 0;
    phead->next = phead;

    return phead;
}

pLink_List_t Create_new_node(int data)
{
    pLink_List_t pnew = (pLink_List_t)malloc(sizeof(Link_List_t));
    if (pnew == NULL)
    {
        perror("malloc a new node fail");
        return NULL;
    }
    Node_num++;
    pnew->prev = NULL;
    pnew->data = data;
    pnew->next = NULL;
    return pnew;    
}

// 头插
#if 1
void Double_Cycle_Link_List_Head_Insert(pLink_List_t phead, pLink_List_t node)
{
    pLink_List_t plink = phead;
    if (node == NULL)
    {
        perror("Head insert a node fail");
        return;
    }
    // 判断是否有首节点
    if (phead->next == phead&&phead->prev==phead)
    {
        plink->prev = node;
        plink->next = node;
        node->prev = phead;
        node->next = phead;
        return;
    }
    // 头插
    //我的头结点的pre不需要动，next需要动
    //插入的node节点prev和next都需要动
    //前节点的prev需要移动到插入的节点上   
    node->next = phead->next;
    node->prev = phead;
    phead->next->prev=node;
    phead->next = node;
    
}
#endif

#if 1
// 尾插
void Double_Cycle_Link_List_Tail_Insert(pLink_List_t phead, pLink_List_t node)
{
    pLink_List_t plink = phead->next;
    if (node == NULL)
    {
        perror("Tail Insert fail");
        return;
    }
    // 判断有无首节点
    if (phead->next == phead)
    {
        plink->next = node;
        plink->prev = node;
        node->next = phead;
        node->prev = phead;
        return;
    }

    // 指针移到最后一个节点
    while (plink->next != phead)
    {
        plink = plink->next;
    }
    node->next=phead;
    node->prev=plink;
    plink->next = node;
    phead->prev = node;
}
#endif

#if 1
// 头删
void Double_Cycle_Link_List_Head_Delet(pLink_List_t phead)
{
    // 是否有首节点
    if (phead->next == phead&&phead->prev==phead)
    {
        return;
    }
   

    pLink_List_t plink = phead->next;
    pLink_List_t temp = phead->next->next;

    //是否为最后一个节点
    if(plink->next==phead)
    {
        phead->next=phead;
        phead->prev=phead;
    }

    free(plink);
    Node_num--;
    phead->next = temp;
    temp->prev = phead;

}
#endif

#if 1
//任意删，用于查找后删除节点
void Double_Cycle_Link_List_Random_Delet(pLink_List_t phead,int data)
{
    pLink_List_t plink=phead;
    pLink_List_t ptemp=NULL;
    //plink指向需要删除节点的前一个节点
    while(plink->next->data!=data)
    {
        if(plink->next==phead)
        {
            printf("链表中无此数据\n");
            return;
        }

        plink=plink->next;
    }
    //ptemp保存要删除的节点的指针 
    ptemp=plink->next;
    ptemp->next->prev=plink;
    plink->next=ptemp->next;
    free(ptemp);
    Node_num--;
    ptemp=NULL;
}
#endif

#if 1
// 尾删
void Double_Cycle_Link_List_Tail_Delet(pLink_List_t phead)
{
    // 判断是否有首节点
    if (phead->next == phead)
    {
        printf("链表不存在首节点");
        return;
    }

    // 判断是否只剩首节点了
    if (phead->next->next == phead)
    {
        free(phead->next);
        Node_num--;
        phead->prev = phead;
        phead->next = phead;
        return;
    }

    pLink_List_t plink = phead->next;
    pLink_List_t ptemp = NULL;

    //找到倒数第二个节点
    while (plink->next->next != phead)
    {
        plink = plink->next;
    }
    //ptemp是尾结点的指针
    ptemp = plink->next;
    plink->next = phead;
    phead->prev = plink;;
    free(ptemp);
    Node_num--;
}
#endif

#if 1
// 查找数据
void Double_Cycle_Link_List_Search(pLink_List_t phead, int data)
{
    if (phead->next == phead)
    {
        printf("链表无首节点");
        return;
    }

    pLink_List_t plink = phead->next;

    while (plink != phead)
    {
        if (plink->data == data)
        {
            printf("已经找到数据%d\n", plink->data);
            return;
        }
        plink = plink->next;
    }

    if (plink == phead)
    {
        printf("链表中找不到此数据\n");
        return;
    }
}
#endif

#if 1
// 修改数据
void Double_Cycle_Link_List_Modify(pLink_List_t phead, int data, int modified_data)
{
    if (phead->next == phead)
    {
        printf("链表首节点");
        return;
    }

    pLink_List_t plink = phead->next;

    while (plink != phead)
    {
        if (plink->data == data)
        {
            plink->data = modified_data;
            return;
        }
        plink = plink->next;
    }

    if (plink == phead)
    {
        printf("链表中找不到此数据\n");
        return;
    }
}
#endif

// 遍历链表
#if 1
void Print_Link_List_next(pLink_List_t phead)
{
    pLink_List_t plink = phead->next;

    if (plink == phead)
    {
        perror("None Link List");
        return;
    }

    while (plink != phead)
    {
        printf("%d  ", plink->data);
        plink = plink->next;
    }
    printf("\n");
}
#endif

#if 1
void Print_Link_List_prev(pLink_List_t phead)
{
    pLink_List_t plink = phead->prev;

    if (plink == phead)
    {
        perror("None Link List");
        return;
    }

    while (plink != phead)
    {
        printf("%d  ", plink->data);
        plink = plink->prev;
    }
    printf("\n");
}
#endif

#if 1
// 释放链表
void Release_Cycle_Link_list(pLink_List_t phead)
{
    pLink_List_t plink = phead->next;
    pLink_List_t ptemp = NULL;

    //不只有头结点的情况
    while (plink != phead)
    {
        ptemp = plink->next;
        free(plink);
        Node_num--;
        plink = ptemp;
    }
    free(phead);
    
    printf("链表已经全部释放\n");
}
#endif


#if 1
//排序，从大到小排
//冒泡排序
void Double_Cycle_Link_list_Sort(pLink_List_t phead)
{
    if( Node_num <= 1 )
    {
        printf("无足够可以排序");
        return;
    }

    for(int i=0;i<Node_num-1;i++)
    {  
        pLink_List_t plink=phead->next;
        pLink_List_t ptemp=plink->next; 
        for(int k=0;k < Node_num-1-i;k++)
        {  
            if( (plink->data) < (ptemp->data) )
            {
                 //更新外围节点
                //前外围节点指向交换后的节点
                //后外围节点指向交换后的节点
                plink->prev->next = ptemp;
                ptemp->next->prev = plink;
                
                // 保存临时指针
                pLink_List_t temp_next = ptemp->next;
                
                // 处理两个交换的节点的next指针域（修改后的两行）
                plink->next = temp_next;
                ptemp->next = plink;

                // 处理两个交换节点的prev指针域（修改后的两行）
                ptemp->prev = plink->prev;
                plink->prev = ptemp;

                //成功交换了的话，第二个节点其实就成为了第一个节点了
                plink = ptemp->next;
                ptemp = plink->next;
            }    
            else{
                plink=plink->next;
                ptemp=plink->next;
            }
            
        }
        printf("第%d次排序:",i);
        Print_Link_List_next(phead);
        printf("\n");

    }
}
#endif



int main()
{
    pLink_List_t phead = NULL;
    phead = Double_Cycle_Link_List_Init();
    Double_Cycle_Link_List_Tail_Insert(phead,Create_new_node(10));
    Double_Cycle_Link_List_Tail_Insert(phead,Create_new_node(40));
    Double_Cycle_Link_List_Tail_Insert(phead,Create_new_node(30));
    Double_Cycle_Link_List_Tail_Insert(phead,Create_new_node(60));
    Double_Cycle_Link_List_Tail_Insert(phead,Create_new_node(50));
    Double_Cycle_Link_List_Tail_Insert(phead,Create_new_node(60));
    Double_Cycle_Link_List_Tail_Insert(phead,Create_new_node(100));
    Double_Cycle_Link_List_Tail_Insert(phead,Create_new_node(80));  
    Print_Link_List_next(phead);
   // Print_Link_List_prev(phead);

    Double_Cycle_Link_list_Sort(phead);
    printf("从大到小排序后的链表为：\n");
    Print_Link_List_next(phead);
    //Print_Link_List_prev(phead);
    printf("一共创建了%d节点\n",Node_num);
    Release_Cycle_Link_list(phead);
    return 0;
}